関係 (集合論)

関係 (集合論) について復習.

一般的な関係

いま, 二つの要素の順序体を $\left\lt a, b\right\gt$ と書くこととする. 他の異なる順序体 $\left\lt c, b\right\gt$ に対し, 以下の通り定義する.

\begin{eqnarray} \left\lt a,b\right\gt=\left\lt c,d\right\gt&:=&a=c, b=d\\\ {\rm デカルト積} = {\rm 直積} = A\times B&:=&\left\{\left\lt a,b\right\gt\mid a\in A, b\in B\right\} \end{eqnarray}

このとき順序体の要素を $n$ 個に拡張したものを $n$-tuple といい, 以下の通り定義する.

$n$-tuple の同値関係と直積

\begin{eqnarray} \left\lt a_1,a_2,\cdots,a_n\right\gt=\left\lt b_1,b_2,\cdots,b_n\right\gt&:=&\left(a_1=b_1,a_2=b_2,\cdots,a_n=b_n\right) \label{eq:first}\tag{1} \\ {\rm デカルト積} = {\rm直積} = A_1\times A_2\times\cdots\times A_n=\prod_{i=1}^{n}A_i&:=&\left\{\left\lt a_1,a_2,\cdots,a_n\right\gt\mid a_1\in A_1,a_2\in A_2,\cdots,a_n\in A_n\right\} \label{eq:second}\tag{2} \end{eqnarray}

なお $\eqref{eq:second}$ より $A^n:=\left(A_1=A_2=\cdots =A_n\right)$ が自明に導ける. いま集合 $A$ から $B$ に対する二項関係 $R\subseteq A\times B$ があって, $\left\lt a,b\right\gt\in R$ ならば $a$ と $b$ は関係 $R$ にあるといい, $R\left(a,b\right)$ または $aRb$ と書く.

\[R:=\left\{\left\lt a,b\right\gt\mid a\in A,b\in B,aRb\right\}\]

$\left(a,b\right)\not\in R$ ならば $a$ と $b$ は関係 $R$ にないといい, $\overline{R}\left(a,b\right)$ または $a\overline{R}b$ と書く. このとき $A=B$ ならば二項関係 $R\subseteq \left(A^2=A\times B\right)$ を $A$ 上の二項関係という¹.

例えば, 自然数の集合 $\mathbb{N}$ に対し, その同値関係 “$=$” を順序体を用いて新たに

\[R:=\left\{\left\lt n,n\right\gt\mid n\in \mathbb{N}\right\}\subseteq\mathbb{N}^2\]

と定義すると $a,b\in \mathbb{N}$ に対して $a R_=b\Leftrightarrow a=b$ である. また, 集合 $X=\left\{1,2,3\right\}$ に対し, その順序関係 $R_\gt\subseteq X^2$ を大なりの関係 “$\gt$” とすると $R_\gt$ は

\[R_\gt=\left\{\left\lt 2,1\right\gt, \left\lt 3,1\right\gt, \left\lt 3,2\right\gt\right\}\]

となる. ここで, 逆関係を導入する. 関係 $R$ の逆関係は $B$ から $A$ への関係, すなわち

\[R^{-1}:=\left\{\left\lt b,a\right\gt\mid a\in A, b\in B, aRb\right\}\]

と定義される. 従って, 例えば集合 $X$ に対する $R_\gt$ の逆関係は $R_\gt^{-1}=\left\{\left\lt 1,2\right\gt, \left\lt 1,3\right\gt, \left\lt 2,3\right\gt\right\}$ である.

二項関係は, より一般化することができる.

$n$ 項関係

いま複数の集合の直積の部分集合, すなわち $n$ 項関係 $R\subseteq\prod_{i=1}^{n}A_i$ があって, $\left\lt a_1,a_2,\cdots,a_n\right\gt\in R$ ならば $a_1,a_2,\cdots,a_n$ は関係 $R$ にあるといい, $R\left(a_1,a_2,\cdots,a_n\right)$ と書く. \[R:=\left\{\left\lt a_1,a_2,\cdots,a_n\right\gt\mid a_1\in A_1,a_2\in A_2,\cdots,a_n\in A_n, R\left(a_1,a_2,\cdots,a_n\right)\right\}\subseteq\prod_{i=1}^{n}A_i\] また $\left\lt a_1,a_2,\cdots,a_n\right\gt\not\subseteq R$ ならば $a_1,a_2,\cdots,a_n$ は関係 $R$ にないといい, $\overline{R}\left(a_1,a_2,\cdots,a_n\right)$ と書く.

ここで, 本ブログ内で特に断りなく使われる一般的な関係に関する記号の表記, その意図について表明しておく.

本ブログで使われる一般的な関係に関する記号表記

任意の二項関係 $\lesssim$ の要素 $\left\lt a,b\right\gt\in\ \lesssim$ に対し:

$\prec\ :=\left\{\left\lt a,b \right\gt\mid \left\lt a, b\right\gt\in\ \lesssim, a\not=b\right\}$
$\ll\ :=\left\{\left\lt a,b\right\gt\mid\left\lt a, c\right\gt\not\in\ \lesssim\ {\rm かつ}\ \left\lt c,b\right\gt\not\in\ \lesssim\right\}$

すなわち, $x\prec y$ は $x$ は真に $y$ の前にある, $x\ll y$ は $x$ は $y$ の直前にあることを意味する.

主な二項関係の規則

主な二項関係における規則を以下に定義する.

反射律

二項関係 $R\subseteq A\times B$, また $x\in A\cap B$ があって, $\left\lt x,x\right\gt\in R$ が存在するとき $R$ は反射律を満たすという.

例えば, 実数の集合 $\mathbb{R}$ をとってみると, 任意の $^\forall x\in\mathbb{R}$ に対して $x\leq x$ であるから $\leq$ は $\mathbb{R}$ の下で反射律を満たす. しかし, $x\lt x$ は成立しないので, $\lt$ は $\mathbb{R}$ の下で反射律を満たさない.

対象律

二項関係 $R\subseteq A\times B$, また $x,y\in A\cap B$ があって, $\left\lt x,y\right\gt\in R$ ならば $\left\lt y,x\right\gt \in R$ が存在するとき, $R$ は対象律を満たすという.

例えば, 実数の集合 $\mathbb{R}$ をとってみると, 自明な例でいえば, 任意の $^\forall x,y\in\mathbb{R}$ に対して $x=y$ ならば $y=x$ なので $=$ は $\mathbb{R}$ の下で対象律を満たす. しかし, $x\lt y$ ならば $y\lt x$ ではないので, $\lt$ は $\mathbb{R}$ の下で対象律を満たさない. また, 別の例として, 例えば平面状のすべての三角形から成る集合 $A$ と, 相似の関係 $R$ を組み合わせると $R$ は $A$ 上で対象律を満たす. \[R=\left\{\left\lt x,y\right\gt\mid x,y\in A,x\ {\rm と}\ y\ {\rm は相似}\right\}\subseteq A^2\] なお, これは同値律を満たす. 対象律の特徴を挙げると:

必ずしも $x=y$ ではない
真に大きい/小さい関係はあり得ない. $R\not=\ \prec$ かつ $R\not=\ \succ$ (すべてのありとあらゆる集合上で $x\prec y ならば y\not\prec x$ なので)

反対象律

二項関係 $R\subseteq A\times B$, また $x,y\in A\cap B$ があって, $\left\lt x,y\right\gt\in R$ に対し $\left\lt y,x\right\gt\in R$ が存在するならば $x=y$ のとき, $R$ は反対象律を満たすという.

例えば, 集合 $A=\left\{a_1,a_2\right\}$ に対して二項関係を:

$R=\left\{\left\lt a_1,a_1\right\gt,\left\lt a_2,a_2\right\gt\right\}$ とおくと, $R$ は $A$ 上で (対象律を満たし) 反対象律を満たす. なお, これは同値律を満たす.
$R=\left\{\left\lt a_1,a_1\right\gt,\left\lt a_1,a_2\right\gt\right\}$ とおくと, $R$ は $A$ 上で (対象律を満たさないが) 反対象律を満たす.
$R=\left\{\left\lt a_1,a_2\right\gt,\left\lt a_2,a_1\right\gt\right\}$ とおくと, $R$ は $A$ 上で (対象律を満たすが) 反対象律を満たさない.

反対象律の特徴を挙げると:

対象的な二項関係が存在するとき, 必ず $x=y$

推移律

二項関係 $R\subseteq A\times B$, また $x,y,z\in A\cap B$ があって, $\left\lt x,y\right\gt,\left\lt y,z\right\gt\in R$ ならば $\left\lt x,z\right\gt \in R$ が存在するとき, $R$ は推移律を満たすという.

例えば, 実数の集合 $\mathbb{R}$ をとってみると, 任意の $^\forall x,y,z\in\mathbb{R}$ に対して $x\leq y$ かつ $y\leq z$ ならば $x\leq z$ なので $\leq$ は $\mathbb{R}$ の下で推移律を満たす. しかし, 例えば自然数の集合 $\mathbb{N}$ に対して

$$R=\left\{\left\lt a, b\right\gt\mid a,b,c\in\mathbb{N}, a=b^2\ {\rm かつ}\ b=c^2\ {\rm ならば}\ a=c^2\ {\rm を満たす}\right\}\subseteq\mathbb{N}^2$$

としたとき, 任意の $x,y\in A$ に対し必ずしも $\left\lt x,y\right\gt\in R$ が存在するとは限らない (反例: $16=4^2$ かつ $4=2^2$ だが $16\not=2^2$) ので, $R$ は $\mathbb{N}$ の下で推移律を満たさない.

主な二項関係

前順序

二項関係 $R$ が集合 $A$ 上で反射律, 推移律を同時に満たすとき, $R$ は $A$ 上の前順序関係という.

これは要するに, じゃんけんのような, 3 すくみ, すなわちグー $\lesssim$ パー $\lesssim$ チョキ $\lesssim$ グー $\lesssim\cdots$ といった循環関係がないこと, グラフで表したときに有向非巡回グラフとなることを要請している.

同値

前順序関係 $R$ が集合 $A$ 上で対象律を満たすとき, $R$ は $A$ 上で同値律を満たすという. また:

$\left\{y\in X\mid xRy\right\}$ を $x$ の同値類といい, $\left[x\right]_R$ や $\left[x\right]$ と書く. このときの $x$ は, 同値類 $\left[x\right]$ の代表元という
集合 $A$ 上の同値関係 $R$ の同値類全体から成る集合 $\left\{[a]\mid a\in A\right\}$ を商集合といい, $A/R$ と書く

まず自明な例でいえば, $=$ は, 空でない任意の集合上で同値関係にあるといえる. ほかに, 例えば, 整数の集合 $\mathbb{Z}$ について $R$ を整数 $p\in\mathbb{Z}$ を法とする合同関係 $\equiv_p$ とおくと, $R$ は $\mathbb{Z}$ 上の同値関係となる. \[R=\equiv_p=\left\{\left\lt m,n\right\gt\mid m,n\in\mathbb{Z}, m {\rm と}\ n\ {\rm は}\ p\ {\rm で割ったときの余りが等しい}\right\}\subseteq\mathbb{Z}^2\] 一つ一つ確認してみると

反射律: 任意の $m\in\mathbb{Z}$ に対して $m-m=0\cdot p$ なので $m\equiv_p m$
推移律: 任意の $m,n,k\in\mathbb{Z}$ に対して $m\equiv_p n$ かつ $n\equiv_p k$ と仮定すると, ある $d,d’\in\mathbb{Z}$ に対して $m-n=d\cdot p$ かつ $n-k=d’\cdot p$ で, このとき $m-k=\left(m-n\right)+\left(n-k\right)=\left(d+d’\right)\cdot p$ である. $d+d’\in\mathbb{Z}$ なので, $m\equiv_p k$
対象律: 任意の $m,n\in\mathbb{Z}$ に対して $m\equiv_p n$ と仮定すると, ある $d\in\mathbb{Z}$ に対して $m-n=d\cdot p$ だから $n-m=(-d)\cdot p$ で, $-d\in\mathbb{Z}$ だから $n\equiv_p m$

と同値律を満たすことがわかる.

同値類や商集合の例として, 集合 $X=\left\{1,3,6,10,11,15,16\right\}\subseteq \mathbb{N}$ の要素 $1$ を代表元とし, いまその同値関係を $5$ を法とした合同²で考えると, $1$ の同値類 $\left[1\right]_R=\left\{x\mid 1\equiv x\pmod{5}\right\}$ は $\left[1\right]_R=\left\{1,6,11,16\right\}$ である³. また,

\begin{eqnarray} \left[1\right]_R&=&\left\{1,6,11,16\right\}\\\ \left[3\right]_R&=&\left\{3\right\}\\\ \left[6\right]_R&=&\left\{1,6,11,16\right\}\\\ \left[10\right]_R&=&\left\{10,15\right\}\\\ \left[11\right]_R&=&\left\{1,6,11,16\right\}\\\ \left[15\right]_R&=&\left\{10,15\right\}\\\ \left[16\right]_R&=&\left\{1,6,11,16\right\} \end{eqnarray}

であるので, $X/R=\left\{\left\{1,6,11,16\right\},\left\{10,15\right\},\left\{3\right\}\right\}$ である.

半順序

前順序関係 $R$ が集合 $A$ 上で反対象律を満たすとき, $R$ は $A$ 上の半順序関係という.

例えば, 集合族上の包含関係 $\subset$ は以下の通り半順序である.

\begin{eqnarray} \begin{array}{l} A\subset A\\ A\subset B{\rm\ かつ}\ B\subset A{\rm\ ならば}\ A=B\\ A\subset B{\rm\ かつ}\ B\subset C{\rm\ ならば}\ A\subset C \end{array} \end{eqnarray}

半順序集合が定義できれば, (最(大|小), 極(大|小))(要素|元)が定義できる.

(最(大|小)|極(大|小))(要素|元)

半順序集合 $A$ の要素 $a_0\in A$ について

$^\exists a\in A\ {\rm s.t.}\ a_0\lesssim a$ なる $a$ が存在しないとき $a_0$ を $A$ の最大(要素|元)といい, $\max A$ と書く. とくに $A$ が複素数の部分集合 $A\subseteq\mathbb{C}$ ならば, $\max A$ を最大値という
$^\exists a\in A\ {\rm s.t.}\ a\lesssim a_0$ なる $a$ が存在しないとき $a_0$ を $A$ の最小(要素|元)といい, $\min A$ と書く. とくに $A$ が複素数の部分集合 $A\subseteq\mathbb{C}$ ならば, $\min A$ を最小値という

また $a\in A$ に対し

$a\gtrsim a_0$ ならば $a=a_0$ のとき $a_0$ を $A$ の極大(要素|元)という
$a\lesssim a_0$ ならば $a=a_0$ のとき $a_0$ を $A$ の極小(要素|元)という

なお最大値, 最小値あるいは極大値, 極小値を総じて extremum という (参考文献 1, 参考文献 2). 例えば, 自然数全体の集合 $\mathbb{N}$ の最小要素は $0$ であるが, 最大要素は存在しない. 実数全体の集合 $\mathbb{R}$ には最(大|小)要素が存在しない⁴. 集合 $X=\left\{x_1,x_2,x_3\right\}$ に対して順序集合 $\left(\wp\left(X\right)-\left\{\emptyset,X\right\},\leq\right)$⁵ の極大要素は $\left\{x_1,x_2\right\},\left\{x_1,x_3\right\},\left\{x_2,x_3\right\}$, また極小要素は $\left\{x_1\right\},\left\{x_2\right\},\left\{x_3\right\}$ である.

半順序集合が定義できれば, (上|下)(界|限)が定義できる.

(上|下)(界|限)

半順序集合 $\left(\wp\left(X\right),\leq\right)$ の空でない部分集合 $A\not =\emptyset$ の任意の要素 $a\in A$ に対し,

$^\exists x\in X\ {\rm s.t.}\ a\lesssim x$ なる $x$ が存在するならば $A$ は上に有界であるといい, $x$ を $A$ の上界という.
$^\exists x\in X\ {\rm s.t.}\ x\gtrsim a$ なる $x$ が存在するならば $A$ は下に有界であるといい, $x$ を $A$ の下界という.
$A$ の上界全体の集合 $B=\left\{x\in X | a\lesssim x\right\}$ の最小要素 $\min B$ を $A$ の上限, または最小上界といい, $\sup A$ と書く.
$A$ の下界全体の集合 $B=\left\{x\in X | x\lesssim a\right\}$ の最大要素 $\max B$ を $A$ の下限, または最大下限といい, $\inf A$ と書く.

例えば, 集合 $X=\left\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots\right\}$ について, 上界および最大値は $\sup A=\max A=1$, 下界は $\inf A=0$, 最小値は存在しないといえる. また, 実数全体の集合 $R$ の空でない部分集合が(上|下)に有界ならば, その(上|下)限が必ず存在する. これは, ワイエルストラスの定理といわれる.

有向 (directed) 集合

集合 $A\not=\emptyset$ と前順序関係 $R$ との組 $\left(A,R\right)$ に対し, $A$ の任意の有限部分集合 $X\subseteq A$ の上界 $\sup X\in A$ が存在するとき, $A$ を有向 (directed) 集合という.

有向集合は, 反対象律を要請されていないので, 必ずしも半順序集合とはならないことに注意. 例えば, 集合 $A=\left\{a_1,a_2,a_3\right\}$ と関係 $R=\left\{\left\lt a_1,a_1\right\gt,\left\lt a_1,a_2\right\gt,\left\lt a_1,a_3\right\gt, \left\lt a_2,a_2\right\gt,\left\lt a_3,a_3\right\gt,\left\lt a_3,a_1\right\gt,\left\lt a_3,a_2\right\gt\right\}$ の組は, 半順序でない有向集合である ($\left\lt a_1,a_3\right\gt,\left\lt a_3,a_1\right\gt\in R$ だが, $a_1=a_3$ は要請していない).

図 1: 集合 $A=\left\{a_1,a_2,a_3\right\}$ と関係 $R=\left\{\left\lt a_1,a_1\right\gt, \left\lt a_1,a_2\right\gt,\left\lt a_1,a_3\right\gt, \left\lt a_2,a_2\right\gt,\left\lt a_3,a_3\right\gt, \left\lt a_3,a_1\right\gt,\left\lt a_3,a_2\right\gt\right\}$ の有向グラフによる図示

全順序

半順序関係 $R$ が集合 $A$ 上の任意の要素に対して比較可能であるとき, $R$ は $A$ 上の全順序関係という.

任意の全順序集合は有向集合である. その他, 例えば, 大小関係 $\leq$ は自然数の集合 $\mathbb{N}$ 上で全順序関係である.

ハッセ図

主に半順序集合の図示の方法としてよく使われるハッセ図について, 以下にいくつかの例を示す.

まずは, 入門書でよく見る例題に習い, 自然数全体の集合 $\mathbb{N}$ の任意の要素 $m,n\in\mathbb{N}$ について, $m$ が $n$ を割り切ることを $m\mid n$ と書くとき⁶, 整除関係 $\mid$ は $\mathbb{N}$ 上の半順序であることに関して考察しよう.

\begin{eqnarray} \begin{array}{l} x\mid x\\ x\mid y{\rm\ かつ}\ y\mid x{\rm\ ならば}\ x=y\\ x\mid y{\rm\ かつ}\ y\mid z{\rm\ ならば}\ x\mid z \end{array} \end{eqnarray}

さて, このような一つの有限半順序集合上の関係は, 図 1 と同様にして, 以下のように有向グラフにより表現できる. いま, 集合 $X=\left\{n\mid n\in\mathbb{N}, 1\leq n\leq 10\right\}$ に対する整除関係による順序を $\ll$ で考えると, $x\mid y$ なら $y$ は必ず $x$ の後に存在する ($x\lesssim y$) ので, 次のような有向非巡回グラフが書ける⁷.

これをハッセ図では次のように書く.

有向グラフが $x\to y$ というように矢印で順序を表しているのに対して, ハッセ図では $y$ を $x$ よりも高い位置に置いて, それぞれを線で結ぶ. このときの最小値および下限は $1$ であり, 上界は $10,8,6,9$ だが $10,8,6,9$ を比較不可能であるため, 上限は存在しない.

別の例として, $X=\left\{a, b, c, d\right\}$ とおいたとき, $a\lesssim c, a\lesssim d, b\lesssim c, b\lesssim d$ という半順序関係にある集合 $\left(X,\lesssim\right)$ を考えると, 以下のように示せる.

図4: 半順序関係 $a\lesssim c, a\lesssim d, b\lesssim c, b\lesssim d$ のハッセ図による図示

このときの下界は $a,b$, 上界は $c,d$ である. 最小元, 最大元, 下限, 上限は $a,b$ および $c,d$ が比較不可能であるため存在しない.

最後にもう 1 つ, 半順序集合 $\left(\wp\left(\left\{x_1,x_2,x_3\right\}\right), \subset\right)$ について考えてみる. 先にも示したように, 集合族上の包含関係 $\subset$ は半順序である. $\emptyset\subset\left\{x_1\right\},\left\{x_1\right\}\subset\left\{x_1,x_2\right\},\cdots$ と考えていくと, ハッセ図は次のようになる.

図5: 半順序集合 $\left(\wp\left(\left\{x_1,x_2,x_3\right\}\right), \subset\right)$ のハッセ図による図示

このときの最小元および下限は $\emptyset$ であり, 最大元および上限は $\left\{x_1,x_2,x_3\right\}$ である.

半順序集合の拡張

有向半順序 (directed partial order) 集合

半順序関係 $R$ と有向集合 $A$ の組 $\left(A, R\right)$ に対し $A$ を有向半順序 dpo (directed partial order) 集合という.

有向完備半順序 (directed complete partial order) 集合

半順序集合 $A$ の任意の有向部分集合 $X\subseteq A$ について, $X$ の上限 $\sup X\in A$ が存在するとき, $A$ を有向完備半順序 dcpo (directed complete partial order) 集合という.

いま $X\subseteq A$ を有限有向部分集合としたとき, 有限半順序集合 $A$ の部分集合 $X$ は, $A$ の半順序関係により必ず有向部分集合となる. つまり, 有限半順序集合は有向完備半順序集合になる. 従って, 図 3, 図 4, 図 5 で示される集合は dcpo 集合である (上記の定義のニュアンスとして, たまに任意の部分集合が有向部分集合でなければならないと捉えられる場合があるが, そうではなく, あくまで有向部分集合として構成可能な部分集合のうちという意味合いである).

完備半順序 (complete partial order) 集合

次の 2 つの条件を満たす半順序集合 $A$ を完備半順序集合 cpo (complete partial order) という.

$A$ は dcpo 集合
$A$ は最小元をもつ

以下にいくつかの例を示す.

図 3 および図 5 で示される集合は dcpo でありかつ最小元をもつため cpo だが, 図 4 は最小元をもたないため, cpo ではない
$\left(\mathbb{N}, \leq\right)$ は, 有向集合として $\mathbb{N}\subseteq\mathbb{N}$ が取れるが, その上限は存在しないので, cpo ではない. ここで, $\infty = \max \mathbb{N}$ となるように拡張した $\left(\mathbb{N}\cup\left\{\infty\right\},\leq\right)$ で考えると, cpo になる.

なお, cpo は上限をもつ $\omega$ 鎖と定義することもできる.

束

二項演算子 $\land,\lor$⁹ のもとで閉じている空でない集合 $L$ の任意の要素 $x,y,z\in L$ に対して, 次の三つの束の公理

可換律:$x\land y=y\land x, x\lor y=y\lor x$
結合律:$\left(x\land y\right)\land z=x\land\left(y\land z\right), \left(x\lor y\right)\lor z=x\lor\left(y\lor z\right)$
吸収律:$x\land\left(x\lor y\right)=x,x\lor\left(x\land y\right)=x$

を満たすとき, 集合 $L$ は束であるといい, $\left(L,\land,\lor\right)$ と表す. ここで $\lor,\land$ はそれぞれ, 結び, 交わりと言われる. いま半順序集合 $S$ の任意の要素 $a,b$ について, 上限を \[\sup\left\{a,b\right\}:=\left\{x\mid ^\forall m\in M\left(x\lesssim m\right),x\in M\right\}, M=\left\{m\mid a,b\lesssim m,m\in S\right\}\] 下限を \[\inf\left\{a,b\right\}:=\left\{x\mid ^\forall m\in M\left(x\gtrsim m\right),x\in M\right\}, M=\left\{m\mid a,b\gtrsim m,m\in S\right\}\] と書くこととすると, $\sup\left\{a,b\right\},\inf\left\{a,b\right\}$ はそれぞれ $a\lor b,a\land b$ と同値である. すなわち, 束とは, $x, y$ について上限と下限が存在する半順序集合のことである¹⁰. また,

束 $L$ の任意の部分集合が上限と下限をもつとき, 束 $L$ をとくに完備束
束の部分集合が束であるとき, その束をとくに部分束
束 $L$ の任意の要素 $^\forall x,y\in L$ について $f\left(x\land y\right)=f\left(x\right)\land f\left(y\right), f\left(x\lor y\right)=f\left(x\right)\lor f\left(y\right)$ を満足する単射 $f: L_1\to L_2$ が存在するとき束 $L_1,L_2$ は同型
束の任意の要素 $x,y,z$ について $x\lor\left(y\land z\right)=\left(x\lor y\right)\land\left(x\lor z\right), x\land\left(y\lor z\right)=\left(x\land y\right)\lor\left(x\land z\right)$ を満たす束をとくに分配束

という.

例えば, 先の例でも挙げた $\left(\wp\left(\left\{x_1,x_2,x_3\right\}\right), \subset\right)$ は束である. 任意の要素として $\left\{x_1\right\},\left\{x_2\right\}$ をとってみると, その上限 $\sup\left\{\left\{x_1\right\},\left\{x_2\right\}\right\}$ は $\left\{x_1\right\}\subset\left\{x_1,x_2\right\},\left\{x_2\right\}\subset\left\{x_1,x_2\right\}$ なので, $\sup\left\{\left\{x_1\right\},\left\{x_2\right\}\right\}=\left\{x_1,x_2\right\}$ である.

図6: 半順序集合 $\left(\wp\left(\left\{x_1,x_2,x_3\right\}\right), \subset\right)$ のハッセ図による図示, $\sup\left\{\left\{x_1\right\},\left\{x_2\right\}\right\}$ を強調

ハッセ図で考えると, 上方向に辺を辿っていったとき, 各ノードそれぞれが順序比較可能でありかつ最小であるものが上限となる. 同様に, 例えば

\begin{eqnarray} \sup\left\{\left\{x_1,x_2\right\},\left\{x_2,x_3\right\}\right\}&=&\left\{x_1,x_2,x_3\right\}\\ \sup\left\{\left\{x_1\right\},\left\{x_2,x_3\right\}\right\}&=&\left\{x_1,x_2,x_3\right\}\\ \sup\left\{\emptyset,\left\{x_1,x_2\right\}\right\}&=&\left\{x_1,x_2\right\}\\ \sup\left\{\emptyset,\emptyset\right\}&=&\emptyset\label{eq:nineth}\tag{9} \end{eqnarray}

となる. 最後の $\eqref{eq:nineth}$ はすべての束の任意の要素について言えることである. すなわち任意の束 $L$ の任意の要素 $x\in L$ に対して $\sup\left\{x,x\right\}=x$ である. これは, 束の公理から導ける, 一般にべき等律といわれる定理である.

証明:

$x,y\in L,z=\left(x\lor y\right)$ に対して

\begin{eqnarray} \sup\left\{x,x\right\}\leftrightarrow x\lor x&=&x\lor\left(x\land\left(x\lor y\right)\right) & \left(\because {\rm \href{#lattice3}{公理3}: 吸収律}\right)\\ &=&x\lor \left(x\land z\right)&\left(\because {\rm \href{#lattice3}{公理3}: 吸収律}\right)\\ &=&x&\left(\because {\rm \href{#lattice3}{公理3}: 吸収律}\right) \end{eqnarray}

$\square$

ここで一度, 上の定理に加えて考察できるいくつかの事項を羅列する.

下限は, 上限の逆順序で定義されるものである. 例えば, $\inf\left\{\left\{x_1\right\},\left\{x_2\right\}\right\}=\emptyset$ である
完備束 $\left(L,\land,\lor\right)$ の任意の部分集合 $S\subseteq L$ に対して $S=\emptyset$ ならば $\sup S=\min L$, $S=L$ ならば $\sup S=\max D$ である

いま, 分配束 $L$ の最大元, 最小元をそれぞれ $1,0$ と書くこととする. 束 $L$ の任意の要素 $x,y\in L$ について $x\lor y=1,x\land y=0$ を満足するとき, $x$ は $y$ の補元といい, $x’$ または $\bar{x}$ と書く. 元 $1,0$ はそれぞれ単位元, 零元である. このときの $L$ の補元は, 唯一に定まる.

証明:

$x,y\in L$ が $a\in L$ の二つの補元だと仮定する.

\begin{eqnarray} x&=&x\lor 0\\ &=&x\lor\left(a\land y\right)\\ &=&\left(x\lor a\right)\land\left(x\lor y\right)\\ &=&1\land\left(x\lor y\right)\\ &=&x\land y \end{eqnarray}

同様に $y=x\lor y$ となるから $x=y$. $\square$

束 $L$ のすべての元が補元をもつとき, $L$ は可補束, または相補束という. 可補分配束は一般にブール代数である¹⁰.

参考文献

Extremum - Wolfram MathWorld 2019/3/15 アクセス.
Maximum and minimum of a function - Encyclopedia of Mathematics 2019/3/15 アクセス.
赤間世紀, 長田康敬, 玉城史朗 (2006)『情報数学入門』共立出版. ISBN-13: 978-4320018143
“Directed complete partial orders”, http://math.chapman.edu/~jipsen/structures/doku.php/directed_complete_partial_orders 2020/7/9 アクセス.

例えば $xy$ 座標平面を $\mathbb{R}^2$ と書くのは, それが実数二つのペアの集合と考えられるからである. ↩
任意の整数 $a,b,c,n\in \mathbb{N}$ に対して
\begin{eqnarray}a\equiv b \pmod n\\\ a\equiv b\pmod n&\rightarrow& b\equiv a\pmod n\\\ a\equiv b, b\equiv c\pmod n &\rightarrow& a\equiv c\pmod n\end{eqnarray}
であることを容易に確かめられる. 従って, 合同は同値関係である. ↩
これをとくに剰余類という. FYI: エルガマル暗号, ガロア体のセクションを参照. ↩
関連: $\epsilon-\delta$ 論法 ↩
ここで, $\wp\left(A\right)$ は $\wp\left(A\right):=\left\{Y\mid Y\subseteq A\right\}$ であり, $A$ の冪集合という. すなわち $A=\left\{a,b\right\}$ とすると $\wp\left(A\right)=\left\{\emptyset,\left\{a\right\},\left\{b\right\},\left\{a,b\right\}\right\}$ となる. いまその要素の個数を $\left|\wp\left(A\right)\right|$ と書くとすると, $\left|\wp\left(A\right)\right|$ は集合 $A$ の全要素の全組み合わせであるので $\left|\wp\left(A\right)\right|={}_3C_0+{}_3C_1+{}_3C_2=7$ となる. 従って, ここで取り上げた例題について丁寧に書き出してみると, \[\wp\left(X\right)-\left\{\emptyset,X\right\}=\left\{X,\left\{x_1,x_2\right\},\left\{x_1,x_3\right\},\left\{x_2,x_3\right\},\left\{x_1\right\},\left\{x_2\right\},\left\{x_3\right\},\emptyset\right\}-\left\{\emptyset,X\right\}\] ということ. ↩
$\mid$ は整数論の界隈で普遍的な記述である. 「割り切れない」も同様にして $\not\mid$ と書いたりする. FYI: エルガマル暗号 ↩
$1$ と自分自身以外の数で割り切れるかを考える. $1$ は始点なので, $1$ のノードへ向けられる辺はないだろう. $2$ について考えてみると, $1\mid 2,3$ なら $1\mid 3$ であるが, $4$ は $1\mid 2\mid 4$ である. これを全要素について適用していくと図のようになる. ↩
論理記号とは無関係であることに注意. ↩
半順序集合 $S$ の任意の要素 $x, y$ に対して $\sup\left\{x,y\right\},\inf\left\{x,y\right\}$ が存在すれば, $x, y$ と順序関係のある $z\in S$ に対して
\begin{eqnarray}\sup\left\{x,y\right\}&=&\sup\left\{y,x\right\}\\ \sup\left\{\sup\left\{x,y\right\},z\right\}&=&\sup\left\{x,\sup\left\{y,z\right\}\right\}\\ \sup\left\{x,\inf\left\{x,y\right\}\right\}&=&x\end{eqnarray}
より束の公理を満たす. 双対の原理より双対についても成り立つ. ↩
可補束ついて次の性質が成り立つ.
\begin{eqnarray}x''&=&x\\ 0'&=&1\\ 1'&=&0\\ x\lor 0&=&x\\ x\land 0&=&0\\ x\lor 1&=&1\\ x\land 1&=&x\\ \left(x\land y\right)'&=&x'\lor y'\\ \left(x\lor y\right)'&=&x'\land y'\\ x\leq y&\leftrightarrow& y'\leq x'\end{eqnarray}
面倒なので証明略. ブール代数のエントリにて分配律を用いずに証明しているものがあるので, それで代用できるかと. ↩

👋New blog information / ブログ移転のお知らせ